Despite the proven importance of fingerprint identification in the fight against crime, nearly all such identification still relies on the Henry system, a manual system for classification and comparison of fingerprints which originated around the turn of the century. Numerous law enforcement agencies throughout the world are in the process of converting from such overburdened manual fingerprint identification and matching systems to high-speed computer based automatic systems.
Automatic fingerprint identification systems, such as the system disclosed in commonly assigned patent application Ser. No. 722,244, filed Sept. 10, 1976, employ fingerprint minutiae based identification and matching wherein data, based upon the location of ridge endings and bifercations, are used to compare an unidentified fingerprint with a library of previously identified fingerprints. However, the fingerprint data base that must be stored to accommodate the accumulated records is so voluminous that even with high-speed electronic circuits, automatic systems that rely solely on minutiae data matching are still not efficient. Accordingly, a reliable classification process has been developed that is conducive to electronic data manipulation and that substantially reduces the data base for each minutiae based matching process.
The function of this automatic classification process is to repeatably and consistently classify individual fingerprints into principal classes which may be described as arch-like, whorl-like and loop-like and to further subdivide each of these classes into subordinate classes which are still relatively insensitive to the normal variations that occur in the process of recording fingerprints.
The present invention is a method and apparatus for performing an important aspect of reliable classification, namely the determination of the location and angular orientation of core and delta singularities. A preferred embodiment of the subject invention is used in achieving highly reliable classification of fingerprint patterns by means of a novel combination of process steps which may be generally characterized in the following manner:
1. Generating an array of quantized ridge contour data from a fingerprint image.
2. Detecting and extracting characteristic singularities and producing a smooth regional contour array from the ridge contour data.
3. Mapping elements of the smooth regional contour array into descriptors which relate to the curvatures and singularities defined by the countour array.
4. Defining a pattern area over which detailed pattern analysis is performed.
5. Identifying sets of contiguous identical descriptors constituting significant regions of curvature and determining size and position information associated with each such region.
6. Performing primary classification to canonical classes.
7. Measuring core-delta distance.
8. Performing subordinate classification of loops and whorls utilizing core-delta distance data.
Cores and deltas, or tri-radii, collectively referred to as singularities, are fundamental elements of the characterization of fingerprints. It is desirable to smooth or filter variations in the ridge contour data caused by a wide variety of noise sources. This smoothing function, which in turn allows the reliable extraction of the location and angular directions of the singularities, is performed by the subject invention, denoted hereinafter as the ANGFLOW circuit.
The ANGFLOW circuit is the foundation of the automatic classifier. It is a two-dimensional filter which quantizes the ridge contour angles into a smaller number of reference directions while at the same time coding regional contour flow in a fixed neighborhood of each contour element into a single new element of data. The ridge contour array may be viewed as a unit amplitude vector field. A two-dimensional smoothing filter examines the correlations which exist in a 5.times.5 window about each contour angle between each of sixteen reference directions and the average ridge flow in that direction. Thus, each ridge contour angle is replaced by an element of a 1, 2, or 3 vector field.
Each element of the new vector field indicates up to three directions which are supported by the surrounding 5.times.5 region. As a result of the procedure of converting to such a vector field, the invention produces one-vector elements in the vicinity of a core or core-like region and three-vector elements in the vicinity of a delta or tri-radial region. The non-singularity regions produce two vectors, not usually 180.degree. apart, which are eventually employed to produce the regional curvature descriptors for use in pattern analysis. The two directions indicate the direction of the surrounding flow. In a region where the flow is straight (uncurved), the elements are 180.degree. apart.
A circular region produces no vectors because no radial directions support flow outward from the center of such a region. Because the 5.times.5 scanning window is used to measure correlations at every ridge contour element, there is an overlap and a resulting generation of clusters of delta and core singularities. The specific points of core and delta singularities are taken at the geometric centroid of the respective clusters. These clusters describe the important fingerprint characteristics used in the classification process. An important structure of a fingerprint for classification is the position and amount of curvature. A whorl has significant recurve on both sides of the core while a loop has a recurve on only one side of the core and an arch has no recurve. It has been found convenient to group similar curves together and identify them by mnemonic letter or symbol.
These symbols fall into categories which provide a local description of the immediate area in which they occur, and when grouped together in clusters also provide a more global description of the fingerprint. A global description of the fingerprint is achieved by examining the relationship of clusters of different descriptors. Examination of the descriptors and their significance leads to construction of canonical forms for each of the main classes of fingerprint classification, namely, arch, tented arch, right loop, left loop, plain whorl, central pocket loop and double loop. Using these canonical forms as models, the classification process examines the regional descriptors for each fingerprint and makes a determination of whether the current print is a reasonable permutation of a canonical form. If the distortion is sufficiently gross to prevent a decision the print is rejected.
The key to reliability of the fingerprint classification process is an accurate determination of the nature and location of singularity points. This accuracy has been achieved in the current invention by means of a unique process involving reference angle correlation to determine the general ridge flow at each point and by a correlation data processing system which determines the number and direction of the correlation peaks. Correlation data processing is accomplished in accordance with a set of restrictive tests which insure a more reliable and accurate evaluation of correlation peaks. The result is a classification system for automatic fingerprint identification which is more reliable and more accurate than all other known prior art classification systems.